pub fn length_of_longest_substring(s: String) -> i32 {
    let mut next: Vec<usize> = Vec::with_capacity(s.len());
    let chars: Vec<char> = s.chars().collect();
    // 求字符的下一个出现的位置
    if s.len() > 0 {
        for i in 0..(s.len() - 1) {
            let mut found = false;
            for j in (i + 1)..s.len() {
                if chars[i] == chars[j] {
                    next.push(j);
                    found = true;
                    break;
                }
            }
            if !found { next.push(s.len()) }
        }
        next.push(s.len())
    }
    let mut max_len: usize = 0;
    for i in 0..s.len() {
        let mut i_max_next = next[i];
        for j in (i + 1)..s.len() {
            if next[j] < i_max_next {
                i_max_next = next[j];
            }
        }
        if max_len < i_max_next - i { max_len = i_max_next - i }
    }
    max_len as i32
}

pub fn length_of_longest_substring_v2(s: String) -> i32 {
    use std::collections::HashMap;
    let mut char_pos: HashMap<char, usize> = HashMap::new();
    let mut max_len: usize = 0;
    let mut doing: usize = 0;
//    println!("{}", s);
    for (i, c) in s.chars().enumerate() {
        if !char_pos.contains_key(&c) || i - doing > char_pos[&c] {
            char_pos.insert(c, i);
            doing += 1;
        } else {
            if doing > max_len {
                max_len = doing;
            }
            let interval = i - char_pos[&c];
            if interval < doing { doing = interval }
            char_pos.insert(c, i);
        }
//        println!("max = {}, doing = {}, {:?}", max_len, doing, char_pos)
    }
    if doing > max_len { max_len = doing }
    max_len as i32
}

#[cfg(test)]
mod tests {
    use crate::{length_of_longest_substring, length_of_longest_substring_v2};

    #[test]
    fn it_works1() {
        let cases = vec![("abcabcbb", 3), ("bbbbb", 1), ("pwwkew", 3), ("", 0), ("cdd", 2), ("dvdf", 3)];
        for (s, expected) in cases {
            assert_eq!(length_of_longest_substring(s.to_string()), expected);
        }
    }

    #[test]
    fn it_works2() {
        let cases = vec![
            ("abcabcbb", 3),
            ("bbbbb", 1),
            ("pwwkew", 3),
            ("", 0),
            ("cdd", 2),
            ("dvdf", 3),
            ("tmmzuxt", 5)];
        for (s, expected) in cases {
            assert_eq!(length_of_longest_substring_v2(s.to_string()), expected);
        }
    }
}
